class Solution
{
    int n;
    vector<vector<string>> ret;
    vector<string> path;
    string _s;
    bool isPalindrome(string& s, int left, int right)
    {
        while (right > left)
        {
            if (s[right--] != s[left++])
            {
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s)
    {
        n = s.size();
        _s = s;
        dfs(0, 0);
        return ret;
    }


    void dfs(int i, int start)
    {
        if (i == n)
        {
            ret.push_back(path);
            return;
        }

        if (i < n - 1)
        {
            dfs(i + 1, start);
        }

        if (isPalindrome(_s, start, i))
        {
            path.push_back(_s.substr(start, i - start + 1));
            dfs(i + 1, i + 1);
            path.pop_back();
        }
    }
};